#include "arrays.h"
#include "algorithmStrings.h"
#include "linklist.h"

namespace algorithm
{
    /**
     * @brief 第1题
     *  此题实现了如何在一个数组中找出两个元素和等于给定值的下标的算法
     * Given nums = [2, 7, 11, 15], target = 9,
     * Because nums[0] + nums[1] = 2 + 7 = 9,
     * return [0, 1]
     *
     * @param vec 待求和的数组
     * @param target 给定的两个元素的和
     * @return vector<int> 返回两个元素的下标
     */
    vector<int> TwoSum(vector<int> vec, int target)
    {
        vector<int> map(vec), index;
        for (int i = 0; i < vec.size(); i++)
        {
            int another = target - vec[i], rst;
            for (int j = 0; j < map.size(); j++)
            {
                if (i == j)
                {
                    continue;
                }
                if (another == map[j])
                {
                    rst = j;
                    index.push_back(i);
                    index.push_back(j);
                    return index;
                }
            }

            /*         vector<int>::iterator rst = find(map.begin(),map.end(),another);
                    int pos = distance(map.begin(),rst);
                    // if (rst != map.end() && vec[i]!=*rst)
                    if (rst != map.end() && pos != i)
                    {
                        index.push_back(i);
                        // index.push_back(rst);
                        cout<<"找到了，第一个元素的下标为"<< *(index.begin())<<endl;
                        index.push_back(distance(map.begin(),rst));
                        cout<<"找到了，第二个元素的下标为"<< index.back()<<endl;
                        break;
                    } */
        }
        return index;
    }

    vector<int> TwoSum1(vector<int> &nums, int target)
    {
        unordered_map<int, int> bitMap;
        for (int i = 0; i < nums.size(); i++)
        {
            auto it = bitMap.find(target - nums[i]);
            // auto it = bitMap.find(target - nums[i]);
            if (it != bitMap.end())
            {
                return {it->second, i};
            }
            bitMap[nums[i]] = i;
        }
        return {};
    }

    double FindMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {
        if (nums1.size() > nums2.size())
        {
            return FindMedianSortedArrays(nums2, nums1);
        }
        int low = 0, high = nums1.size(), k = (nums1.size() + nums2.size() + 1) >> 1, nums1Mid = 0, nums2Mid = 0;
        while (low <= high)
        {
            nums1Mid = low + (high - low) >> 1;
            nums2Mid = k - nums1Mid;
            if (nums1Mid > 0 && nums1[nums1Mid - 1] > nums2[nums2Mid])
            {
                high = nums1Mid - 1;
            }
            else if (nums1Mid != nums1.size() && nums1[nums1Mid] < nums2[nums2Mid - 1])
            {
                low = nums1Mid + 1;
            }
            else
            {
                break;
            }
        }
        int midLeft = 0, midRight = 0;
        if (nums1Mid == 0)
        {
            midLeft = nums2[nums2Mid - 1];
        }
        else if (nums2Mid == 0)
        {
            midLeft = nums1[nums1Mid - 1];
        }
        else
        {
            midLeft = (nums1[nums1Mid - 1] > nums2[nums2Mid - 1]) ? nums1[nums1Mid - 1] : nums2[nums2Mid - 1];
        }

        if ((nums1.size() + nums2.size()) & 0x01 == 0x01)
        {
            return double(midLeft);
        }
        if (nums1Mid == nums1.size())
        {
            midRight = nums2[nums2Mid];
        }
        else if (nums2Mid == nums2.size())
        {
            midRight = nums1[nums1Mid];
        }
        else
        {
            midRight = (nums1[nums1Mid] < nums2[nums2Mid]) ? nums1[nums1Mid] : nums2[nums2Mid];
        }
        return double(midLeft + midRight) / 2.0;
    }

    /*     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int tot = nums1.size() + nums2.size();
            if (tot % 2 == 0) {
                int left = find(nums1, 0, nums2, 0, tot / 2);
                int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
                return (left + right) / 2.0;
            } else {
                return find(nums1, 0, nums2, 0, tot / 2 + 1);
            }
        }

        int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
            if (nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);
            if (k == 1) {
                if (nums1.size() == i) return nums2[j];
                else return min(nums1[i], nums2[j]);
            }
            if (nums1.size() == i) return nums2[j + k - 1];
            int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
            if (nums1[si - 1] > nums2[sj - 1])
                return find(nums1, i, nums2, sj, k - (sj - j));
            else
                return find(nums1, si, nums2, j, k - (si - i));
        } */

    /**
     * @brief 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
     * 如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
     * 假设环境不允许存储 64 位整数（有符号或无符号）。
     * 输入：x = 123
     * 输出：321
     * @param num 输入的整数
     * @return int 返回反转后的整数
     */
    int ReverseInt(int num)
    {
        int64_t rst = 0;
        while (num != 0)
        {
            int mod = num % 10;
            num /= 10;
            rst = rst * 10 + mod;
        }
        if (rst > pow(2, 31) - 1 || rst < -1 * pow(2, 31))
            rst = 0;
        return rst;
    }

    /**
     * @brief 请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
     * 函数 myAtoi(string s) 的算法如下：
     *     读入字符串并丢弃无用的前导空格
     *     检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。
     *  确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
     *  读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
     *  将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有
     * 读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
     *     如果整数数超过 32 位有符号整数范围 [−2^31,  2^31 − 1] ，需要截断这个整数，
     * 使其保持在这个范围内。具体来说，小于 −2^31 的整数应该被固定为 −2^31 ，大于 2^31 − 1 的整数应该被固定为 2^31 − 1 。
     * 返回整数作为最终结果。
     *
     * 注意：
     *     本题中的空白字符只包括空格字符 ' ' 。
     *     除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
     *
     * @param s
     * @return int
     */

    int myAtoi(string s)
    {
        /**
         * @brief 操作步骤
         * 1.去除前导符，即空格
         * 2.判断正负号，记录下正负号；当出现正负号时，意味着后面必须是数字，否则返回零；
         * 3.从正负号后面的数字开始算，当是数字，是有ans=10+当前数字,在用此操作之前，要判断ans是否越界
         * 4.加上符号做为最终运算结果返回。
         */
        int idx = 0;
        const int sLen = s.length();
        while (idx < sLen && s[idx] == ' ')
        {
            idx++;
        }
        if (idx == sLen)
        {
            return 0;
        }
        bool negative = false;
        if (s[idx] == '-')
        {
            negative = true;
            idx++;
        }
        else if (s[idx] == '+')
        {
            idx++;
        }
        else if (s[idx] > '9' || s[idx] < '0')
        {
            return 0;
        }
        int ans = 0;
        while (idx < sLen && s[idx] <= '9' && s[idx] >= '0')
        {
            int digit = s[idx] - '0';
            if (ans > (pow(2, 31) - 1 - digit) / 10)
                return negative ? -pow(2, 31) : pow(2, 31) - 1;
            ans = ans * 10 + digit;
            idx++;
        }
        return negative ? -ans : ans;
    }


    /**
     * @brief 测试第2题的算法
     *
     */
    void TestAddTwoNumbs()
    {
        vector<int> v1{1, 3, 6, 4, 5, 2, 9};
        vector<int> v2{9, 9, 9, 9};
        linkNode<int> *lst1 = linkList<int>(v1).GetList();
        linkNode<int> *lst2 = linkList<int>(v2).GetList();

        vector<int> idx = TwoSum1(v1, 13);
        for (vector<int>::iterator it = idx.begin(); it < idx.end(); it++)
        {
            std::cout << *it << std::endl;
        }

        string s = LongestPalindrome2("aabad");
        std::cout << s << std::endl;

        linkNode<int> *lst = AddTwoNums(lst1, lst2);
        string istr = "PAYPALISHIRING";
        for (int i = 0; i < istr.length(); i++)
        {
            std::cout << istr[i] << " -> ";
        }
        std::cout << "end" << std::endl;

        s = Convert(istr, 3);
        // if (s == "PAHNAPLSIIGYIR")
        std::cout << s << std::endl;
        for (int i = 0; i < s.length(); i++)
        {
            std::cout << s[i] << " -> ";
        }
        std::cout << "end" << std::endl;

        // 测试 ReverseInt()
        int num = ReverseInt(153469);
        // std::cout <<"ReverseInt 测试: " << num << std::endl;

        int myInt = myAtoi("-91283472332");
        // std::cout << "MyAtoi 测试: " << myInt << std::endl;

        bool is=isPalindrome(101);
        std::cout << "回文数字测试: " << is << std::endl;

        int len = GetLenOfLongestSubstring("aabbcefdurec");
        // std::cout << len << std::endl;
        return;
    }
}